﻿#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

#if 0
//namespace ouyang
//{
//	typedef pair<const Key, T> value_type;
//
//	template <class T1, class T2>
//	struct pair
//	{
//		typedef T1 first_type;
//		typedef T2 second_type;
//		T1 first;
//		T2 second;
//		pair() : first(T1()), second(T2())
//		{}
//		pair(const T1& a, const T2& b) : first(a), second(b)
//		{}
//		template<class U, class V>
//		pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
//		{}
//	};
//
//	template <class T1, class T2>
//	inline pair<T1, T2> make_pair(T1 x, T2 y)
//	{
//		return (pair<T1, T2>(x, y));
//	}
//}
#endif

//int main()
//{
	//template < class T,          // set::key_type/value_type
	//	class Compare = less<T>,   // set::key_compare/value_compare
	//	class Alloc = allocator<T> // set::allocator_type
	//> class set;
	// T是类型，Compare是比较的仿函数，Alloc是空间配置器

	// set只可以增删查，改会破坏结构
	// 构造方面：区间/默认构造
	// less<int>升序， greater<int>降序
	//set<int, greater<int>> myset1;    // 默认
	//set<int> myset2{ 1, 2, 3, 4, 5 };    // 区间
	//// 拷贝构造
	//set<int, greater<int>> myset3(myset1);


	//myset1.insert(1);
	//myset1.insert(2);
	//myset1.insert(4);
	//myset1.insert(4);
	//myset1.insert(6);

	//myset3.insert({ 1, 2, 4, 4, 6 });


	// 去重 + 升序(默认)
	/*cout << "myset1: ";
	for (auto e : myset1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "myset2: ";
	for (auto e : myset2)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "myset3: ";
	for (auto e : myset3)
	{
		cout << e << " ";
	}*/


	// set::find
	// 查找val，返回val所在的迭代器，没有找到返回end()
	/*iterator find(const value_type & val);*/
	//int x = 0;
	#if 0	
	// 输入ctrl+z即可退出
	while (cin >> x)
	{
		if (myset1.find(x) != myset1.end())
			cout << "找到了" << endl;
		else
			cout << "不存在" << endl;
	}
	#endif

	// set::count
	// 查找val，返回Val的个数,count可以用于判断数据是否存在于set中
	/*size_type count(const value_type & val) const;*/ 
#if 0
	while (cin >> x)
	{
		if (myset1.count(x))
			cout << "找到了" << endl;
		else
			cout << "不存在" << endl;
	}
#endif

	// set::erase
	// 删除⼀个迭代器位置的值
	///*iterator erase(const_iterator position);*/
	// 删除val，val不存在返回0，存在返回1
	///*size_type erase(const value_type & val);*/
	// 删除⼀段迭代器区间的值
	///*iterator erase(const_iterator first, const_iterator last);*/


	//myset1.erase(myset1.begin());
	//cout << "myset1: ";
	//for (auto e : myset1)
	//{
	//	cout << e << " ";
	//}
	//cout << endl;

	//// 全部删除
	//auto it = myset1.begin();
	//while (it != myset1.end())
	//{
	//	it = myset1.erase(it);
	//}
	//cout << "myset1: ";
	//for (auto e : myset1)
	//{
	//	cout << e << " ";
	//}


	/* 直接删除x
	cin >> x;
	int num = myset1.erase(x);
	if (num == 0)
	{
		cout << x << "不存在！" << endl;
	} 
	for (auto e : myset1)
	{
		cout << e << " ";
	} 
	cout << endl;*/

#if 0
	// 区间删除
	// 删除⼀段迭代器区间的值
	/*iterator erase(const_iterator first, const_iterator last);*/
	// 返回⼤于等val位置的迭代器
	/*iterator lower_bound(const value_type & val) const;*/
	// 返回⼤于val位置的迭代器
	/*iterator upper_bound(const value_type & val) const;*/
	set<int> myset;
	for (int i = 10; i <= 100; i += 10) // 10~100
	{
		myset.insert(i);
	}
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	// 删除30~50区间的数

	auto it_left = myset.lower_bound(30); // >=30位置的迭代器
	set<int>::iterator it_right = myset.upper_bound(50); // >50位置的迭代器
	myset.erase(it_left, it_right);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;


	// 删除15~75区间的数
	auto it_left = myset.lower_bound(15); // >=30位置的迭代器
	set<int>::iterator it_right = myset.upper_bound(75); // >50位置的迭代器
	myset.erase(it_left, it_right);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;


	// multiset和set的差异
	// multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余
	// insert可以插入重复的值,find返回查找x中序遍历的值的第一个,erase会删除所有的x
	multiset<int> mymultiset{ 1,1,2,3,4,4,4,5,6 };
	for (auto e : mymultiset)
	{
		cout << e << " ";
	}
	cout << endl;

	// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个
	cin >> x;
	auto pos = mymultiset.find(x);
	while (pos != mymultiset.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	} 
	cout << endl;

	// 相⽐set不同的是，count会返回x的实际个数
	cout << mymultiset.count(x) << endl;

	// 相⽐set不同的是，erase给值时会删除所有的x
	mymultiset.erase(x);
	for (auto e : mymultiset)
	{
		cout << e << " ";
	} 
	cout << endl;
#endif
//
//	return 0;
//}
#if 0
// 两个数的交集
// https://leetcode.cn/problems/intersection-of-two-arrays/

class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		set<int> s1(nums1.begin(), nums1.end());
		set<int> s2(nums2.begin(), nums2.end());
		vector<int> ret;
		auto it1 = s1.begin();
		auto it2 = s2.begin();
		while (it1 != s1.end() && it2 != s2.end())
		{
			if (*it1 > *it2)
			{
				++it2;
			}
			else if (*it1 < *it2)
			{
				++it1;
			}
			else {
				ret.push_back(*it1);
				++it1;
				++it2;
			}
		}
		return ret;
	}
};


// 环形链表II
// https://leetcode.cn/problems/linked-list-cycle-ii/
class Solution {
public:
	ListNode* detectCycle(ListNode* head) {
		set<ListNode*> myset;
		ListNode* cur = head;
		while (cur)
		{
			if (myset.count(cur))
				return cur;
			else
				myset.insert(cur);
			cur = cur->next;
		}
		return nullptr;
	}
};
#endif

//int main()
//{
	// map::construct 构造方式
	//  empty (1) ⽆参默认构造
	///*explicit map(const key_compare & comp = key_compare(),
	//const allocator_type & alloc = allocator_type());*/
	// range (2) 迭代器区间构造
	///*template <class InputIterator>
	//map(InputIterator first, InputIterator last,
	//const key_compare & comp = key_compare(),
	//const allocator_type & = allocator_type());*/
	// copy (3) 拷⻉构造
	///*map(const map & x);*/
	// initializer list (5) initializer 列表构造
	///*map(initializer_list<value_type> il,
	//	const key_compare & comp = key_compare(),
	//	const allocator_type & alloc = allocator_type());*/
	// explicit防止隐式类型转换
#if 0
	map<string, string> dict1;
	map<string, string> dict2{ {"left", "左边"}, {"right", "右边"}};
	map<string, string> dict3(dict1);


	// 范围for，由于是pair类型，内部有多个元素
	for (auto& e : dict1)
	{
		cout << e.first << " " << e.second << endl;
	}
	cout << endl;

	// 迭代器查询
	auto it2 = dict2.begin();
	while (it2 != dict2.end())
	{
		cout << it2->first << " " << it2->second << endl;
		it2++;
	}
	cout << endl;

	// 迭代器查询
	auto it3 = dict3.begin();
	while (it3 != dict3.end())
	{
		cout << (*it3).first << " " << (*it3).second << endl;
		++it3;
	}
	cout << endl;
#endif

	// map::insert
	// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
	///*pair<iterator, bool> insert(const value_type & val);*/
	///*我们可以看到在我们插入一个数据时，如果这个数据不存在，
	//我们插入后会返回 iterator::当前插入数据的迭代器，bool::true*/
	///*如果这个数据存在，那么我们会插入失败，返回的iterator::是该存在数据的迭代器，bool::false*/
	// 所以inert还存在查找的功能
#if 0
	mapped_type& operator[] (const key_type& k);
	// operator的内部实现
	mapped_type& operator[] (const key_type& k)
	{
		// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
		mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能
		// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
		迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能
		pair<iterator, bool> ret = insert({ k, mapped_type() });
		iterator it = ret.first;
		return it->second;
	}

	map<string, string> dict;
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1);
	dict.insert(pair<string, string>("second", "第二个"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert({ "auto", "自动的" });
	// "left"已经存在，插⼊失败
	dict.insert({ "left", "左边，剩余" });
	// 范围for遍历
	for (const auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	} 
	cout << endl;
	string str;
	while (cin >> str)
	{
		auto ret = dict.find(str);
		if (ret != dict.end())
		{
			cout << "->" << ret->second << endl;
		} 
		else
		{
		cout << "无此单词，请重新输入" << endl;
		}
	} 

	// erase等接⼝跟set完全类似
		
	// c++11
	// 列表插⼊，已经在容器中存在的值不会插⼊
	/*void insert(initializer_list<value_type> il);*/
	// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
	/*template <class InputIterator>
	void insert(InputIterator first, InputIterator last);*/
	
	string S_fruit[]{ "苹果", "香蕉", "苹果", "梨子", "西瓜", "香蕉", "苹果" };
	map<string, int> fruits;
	for (auto& e : S_fruit)
	{
		auto it = fruits.find(e);
		if (it == fruits.end())
		{
			fruits.insert({ e, 1 });
		}
		else {
			it->second++;
		}
	}

	for (const auto & e : fruits)
	{
		cout << e.first << ":" << e.second << endl;
	} 
	cout << endl;

	for (auto& e : S_fruit)
	{
		// []先查找⽔果在不在map中
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了
		// 2、在，则返回⽔果对应的次数++
		fruits[e]++; // 插入+查找+修改的功能
	}

	for (const auto& e : fruits)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
#endif
	//map<string, string> dict;
	//dict.insert(make_pair("sort", "排序"));
	//// key不存在->插⼊ {"insert", string()}
	//dict["insert"];
	//// 插⼊+修改
	//dict["left"] = "左边";
	//// 修改
	//dict["left"] = "左边、剩余";
	//// key存在->查找
	//cout << dict["left"] << endl;

	// multimap和map的区别
	///*multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
	//insert / find / count / erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如
	//find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改。*/

	// 随机链表的复制
	// https://leetcode.cn/problems/copy-list-with-random-pointer/description/
#if 0
	class Solution {
	public:
		Node* copyRandomList(Node* head)
		{
			map<Node*, Node*> Nodemap;
			Node* cur = head;
			Node* Copyhead = nullptr, * Copytail = nullptr;
			// 复制拷贝链表
			while (cur)
			{
				if (Copyhead == nullptr)
				{
					Copyhead = Copytail = new Node(cur->val);
				}
				else {
					Copytail->next = new Node(cur->val);
					Copytail = Copytail->next;
				}
				Nodemap[cur] = Copytail;
				cur = cur->next;
			}
			// 连接随机random
			cur = head;
			Node* Copy = Copyhead;
			while (cur)
			{
				if (cur->random == nullptr)
				{
					Copy->random = nullptr;
				}
				else {
					Copy->random = Nodemap[cur->random];
				}
				cur = cur->next;
				Copy = Copy->next;
			}
			return Copyhead;
		}
};


	// 前k个高频单词
	// https://leetcode.cn/problems/top-k-frequent-words/description/
	// 解法一：
	class Solution {
	public:

		struct Compare {
			bool operator()(const pair<string, int>& x1, const pair<string, int>& x2) const
			{
				return x1.second > x2.second;
			}
		};

		vector<string> topKFrequent(vector<string>& words, int k)
		{
			vector<string> ret;
			map<string, int> dict;
			for (auto& word : words)
			{
				dict[word]++;
			}

			vector<pair<string, int>> v(dict.begin(), dict.end());
			stable_sort(v.begin(), v.end(), Compare());

			for (int i = 0; i < k; ++i)
			{
				ret.push_back(v[i].first);
			}

			return ret;
		}
	};

	// 解法二：
	class Solution {
	public:

		struct Compare
		{
			bool operator()(const pair<string, int>& x1, const pair<string, int>& x2) const
			{
				// 要注意优先级队列底层是反的，⼤堆要实现⼩于⽐较，所以这⾥次数相等，
				// 想要字典序⼩的在前⾯要⽐较字典序⼤的为真
				return x1.second < x2.second || (x1.second == x2.second && x1.first > x2.first);
			}
		};

		vector<string> topKFrequent(vector<string>& words, int k)
		{
			map<string, int> dict;
			for (auto& w : words)
			{
				dict[w]++;
			}

			priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> q(dict.begin(), dict.end(), Compare());

			vector<string> ret;
			for (int i = 0; i < k; ++i)
			{
				ret.push_back(q.top().first);
				q.pop();
			}
			return ret;
		}
	};
#endif

